package algorithm.tree;

import algorithm.model.TreeNode;

/**
 * leetcode
 * https://leetcode.com/problems/longest-univalue-path/
 * Easy
 *
 * 给一个二叉树，树的节点上都有值
 * 找到值都一样的，最长的路径。这个路径的起点和终点都不一定在root和leaf，可以在中间
 *
 * Created by yzy on 2020-04-12 22:25
 */
public class LongestUnivaluePath {

    public static void main(String[] args) {
//        TreeNode node = TreeNode.getTreeNode(new Integer[]{5,4,5,1,1,5});
//        System.out.println(node);
//        System.out.println(longestUnivaluePath(node));

        TreeNode node_1 = TreeNode.getTreeNode(new Integer[]{1});
        System.out.println(longestUnivaluePath_global_var(node_1));
    }


    /**
     * RumTime: 2ms, 96.03%
     * Memory: 42MB, 100.0%
     */
    static int maxPath=0;
    public static int longestUnivaluePath_global_var(TreeNode root) {
        if (root == null) return 0;
        getMaxPath(root, root.val);
        return maxPath;
    }

    /**
     * 以当前node为根节点，往下找，返回的结果是：路过该根节点，连接左右子树，相同值最长的路径
     * 同时，在方法中，更新maxPath的全局变量。
     * 当遍历完时，也就找到了最大值。
     * @param node
     * @param parentVal
     * @return
     */
    public static int getMaxPath(TreeNode node, int parentVal){
        if (node == null) return 0;
        int currVal = node.val;
        int left = getMaxPath(node.left, currVal);
        int right = getMaxPath(node.right, currVal);
        maxPath = Math.max(maxPath, (left + right));
        if (parentVal == node.val)  {
            return Math.max(left, right) + 1;
        }
        return 0;
    }



    /**
     * Runtime: 6ms, 8.84%
     * Memory: 42.2MB 100.0%
     *
     * 思路：
     * DFS 加 递归
     * 没有全局变量
     *
     * lup[node] 表示以该节点为root的，lup的结果
     * lp[node] 表示路过该节点。以该节点为root的，值为roo.val的。最长路径结果
     * fmp[node, val] 表示以该节点为root的，往下走值为val的最长路径
     *
     * fmp[node, val] = {
     *     if(node.val != val) return 0;
     *     return 1 + Math.max(fmp[node.left, val], fmp[node.right, val]);
     * }
     *
     * lp[node] = fmp[node.left, val] + fmp[node.right, val]
     * 那么：
     * lup[root] = Math.max(fmp[root], lup[roo.left], lup[right])
     * @param root
     * @return
     */
    public static int longestUnivaluePath(TreeNode root) {
        if(root==null) return 0;
        int rootPath = findMaxPath(root.left, root.val) + findMaxPath(root.right, root.val);
        int leftPath = longestUnivaluePath(root.left);
        int rightPath = longestUnivaluePath(root.right);
        return Math.max(rootPath, Math.max(leftPath, rightPath));
    }


    /**
     * 找出，以该节点为起点的，往下等于pathVal的，最长的路径
     * 要加1，是因为要算上当前节点的长度
     * @param root
     * @return
     */
    public static int findMaxPath(TreeNode root, int pathVal){
        if(root==null || pathVal!=root.val) return 0;
        return 1 + Math.max(findMaxPath(root.left, pathVal), findMaxPath(root.right, pathVal));
    }
}
